<!DOCTYPE html>
<html lang="zh-CN">

<head>
  <meta charset="UTF-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>混合图布局算法对比</title>
  <script src="https://cdnjs.cloudflare.com/ajax/libs/d3/7.8.5/d3.min.js"></script>
  <style>
    body {
      font-family: 'Arial', sans-serif;
      margin: 0;
      padding: 20px;
      background: linear-gradient(135deg, #667eea 0%, #764ba2 100%);
      min-height: 100vh;
    }

    .container {
      max-width: 1400px;
      margin: 0 auto;
      background: rgba(255, 255, 255, 0.95);
      border-radius: 20px;
      padding: 30px;
      box-shadow: 0 20px 40px rgba(0, 0, 0, 0.1);
    }

    h1 {
      text-align: center;
      color: #2c3e50;
      margin-bottom: 30px;
      font-size: 2.5em;
      text-shadow: 2px 2px 4px rgba(0, 0, 0, 0.1);
    }

    .controls {
      display: flex;
      justify-content: center;
      gap: 15px;
      margin-bottom: 30px;
      flex-wrap: wrap;
    }

    button {
      background: linear-gradient(45deg, #667eea, #764ba2);
      color: white;
      border: none;
      padding: 12px 24px;
      border-radius: 25px;
      cursor: pointer;
      font-size: 16px;
      font-weight: bold;
      transition: all 0.3s ease;
      box-shadow: 0 4px 15px rgba(102, 126, 234, 0.3);
    }

    button:hover {
      transform: translateY(-2px);
      box-shadow: 0 6px 20px rgba(102, 126, 234, 0.4);
    }

    .layout-container {
      display: grid;
      grid-template-columns: repeat(auto-fit, minmax(400px, 1fr));
      gap: 30px;
      margin-top: 30px;
    }

    .layout-section {
      background: white;
      border-radius: 15px;
      padding: 20px;
      box-shadow: 0 10px 30px rgba(0, 0, 0, 0.1);
      border: 2px solid #e0e0e0;
      transition: transform 0.3s ease;
    }

    .layout-section:hover {
      transform: translateY(-5px);
      box-shadow: 0 15px 40px rgba(0, 0, 0, 0.15);
    }

    .layout-title {
      text-align: center;
      font-size: 1.5em;
      font-weight: bold;
      margin-bottom: 15px;
      color: #2c3e50;
    }

    .stats {
      background: #f8f9fa;
      padding: 15px;
      border-radius: 10px;
      margin-top: 15px;
      border-left: 4px solid #667eea;
    }

    .stat-item {
      display: flex;
      justify-content: space-between;
      margin-bottom: 8px;
      font-size: 14px;
    }

    .stat-label {
      font-weight: bold;
      color: #555;
    }

    .stat-value {
      color: #667eea;
      font-weight: bold;
    }

    svg {
      width: 100%;
      height: 400px;
      border: 1px solid #ddd;
      border-radius: 10px;
      background: radial-gradient(circle at center, #ffffff 0%, #f8f9fa 100%);
    }

    .node {
      stroke: white;
      stroke-width: 2px;
      cursor: pointer;
      transition: all 0.3s ease;
    }

    .node:hover {
      stroke-width: 3px;
      r: 8px;
    }

    .link {
      stroke: #999;
      stroke-opacity: 0.6;
      stroke-width: 1px;
    }

    .community-0 {
      fill: #ff6b6b;
    }

    .community-1 {
      fill: #4ecdc4;
    }

    .community-2 {
      fill: #45b7d1;
    }

    .community-3 {
      fill: #96ceb4;
    }

    .community-4 {
      fill: #feca57;
    }

    .community-5 {
      fill: #ff9ff3;
    }

    .community-6 {
      fill: #54a0ff;
    }

    .community-7 {
      fill: #5f27cd;
    }

    /* 图例颜色样式 */
    .legend-color.community-0 {
      background-color: #ff6b6b;
    }

    .legend-color.community-1 {
      background-color: #4ecdc4;
    }

    .legend-color.community-2 {
      background-color: #45b7d1;
    }

    .legend-color.community-3 {
      background-color: #96ceb4;
    }

    .legend-color.community-4 {
      background-color: #feca57;
    }

    .legend-color.community-5 {
      background-color: #ff9ff3;
    }

    .legend-color.community-6 {
      background-color: #54a0ff;
    }

    .legend-color.community-7 {
      background-color: #5f27cd;
    }

    .legend {
      margin-top: 15px;
      display: flex;
      flex-wrap: wrap;
      gap: 15px;
      justify-content: center;
    }

    .legend-item {
      display: flex;
      align-items: center;
      gap: 8px;
      font-size: 12px;
    }

    .legend-color {
      width: 12px;
      height: 12px;
      border-radius: 50%;
      border: 1px solid #ccc;
    }
  </style>
</head>

<body>
  <div class="container">
    <h1>🔄 混合图布局算法对比可视化</h1>

    <div class="controls">
      <button onclick="generateNewData()">🎲 生成新数据</button>
      <button onclick="toggleAnimation()">⚡ 切换动画</button>
      <button onclick="exportResults()">📊 导出结果</button>
    </div>

    <div class="layout-container" id="layoutContainer">
      <!-- 布局将动态生成 -->
    </div>
  </div>

  <script>
    class GraphLayoutComparison {
      constructor() {
        this.currentDataset = 0;
        this.datasets = [];
        this.animationEnabled = true;
        this.results = [];
        this.generateInitialDatasets();
        this.render();
      }

      // 生成随机图数据
      generateRandomGraph() {
        const nodeCount = Math.floor(Math.random() * 20) + 30; // 30-50个节点
        const nodes = [];
        const edges = [];

        // 创建节点并分配社区
        const communityCount = Math.floor(Math.random() * 3) + 4; // 4-6个社区
        for (let i = 0; i < nodeCount; i++) {
          nodes.push({
            id: i,
            community: Math.floor(Math.random() * communityCount),
            importance: Math.random() // 节点重要性
          });
        }

        // 创建边，社区内连接概率更高
        for (let i = 0; i < nodeCount; i++) {
          for (let j = i + 1; j < nodeCount; j++) {
            let probability = 0.1; // 基础连接概率
            if (nodes[i].community === nodes[j].community) {
              probability = 0.4; // 社区内连接概率
            }

            if (Math.random() < probability) {
              edges.push({
                source: i,
                target: j
              });
            }
          }
        }

        return { nodes, edges };
      }

      // 生成10组初始数据
      generateInitialDatasets() {
        this.datasets = [];
        for (let i = 0; i < 10; i++) {
          this.datasets.push(this.generateRandomGraph());
        }
      }

      // 混合布局算法
      hybridLayout(graph, width, height) {
        const { nodes, edges } = JSON.parse(JSON.stringify(graph));
        const centerX = width / 2;
        const centerY = height / 2;
        const maxRadius = Math.min(width, height) * 0.4;

        // 按社区分组
        const communities = {};
        nodes.forEach(node => {
          if (!communities[node.community]) {
            communities[node.community] = [];
          }
          communities[node.community].push(node);
        });

        // 为每个社区分配层次
        Object.values(communities).forEach(community => {
          community.forEach(node => {
            // 基于重要性和连接数分配层次 (0-5层)
            const connections = edges.filter(e =>
              e.source === node.id || e.target === node.id
            ).length;
            node.layer = Math.min(5, Math.floor(
              (1 - node.importance) * 3 +
              Math.max(0, (connections - 2)) * 0.5
            ));
          });
        });

        // 为每个社区分配角度扇区
        const communityKeys = Object.keys(communities);
        const anglePerCommunity = (2 * Math.PI) / communityKeys.length;

        communityKeys.forEach((communityId, index) => {
          const community = communities[communityId];
          const baseAngle = index * anglePerCommunity;

          // 按层次分组
          const layers = {};
          community.forEach(node => {
            if (!layers[node.layer]) layers[node.layer] = [];
            layers[node.layer].push(node);
          });

          // 为每层节点分配位置
          Object.entries(layers).forEach(([layer, layerNodes]) => {
            const layerRadius = maxRadius * (parseInt(layer) + 1) / 6;
            const angleSpread = anglePerCommunity * 0.8; // 留一些间隙

            layerNodes.forEach((node, nodeIndex) => {
              // 在社区扇区内均匀分布，并添加一些随机偏移减少边交叉
              const nodeAngle = baseAngle +
                (angleSpread * nodeIndex / Math.max(1, layerNodes.length - 1)) -
                angleSpread / 2 +
                (Math.random() - 0.5) * 0.2; // 小的随机偏移

              node.x = centerX + layerRadius * Math.cos(nodeAngle);
              node.y = centerY + layerRadius * Math.sin(nodeAngle);
            });
          });
        });

        return { nodes, edges };
      }

      // 圆形布局
      circularLayout(graph, width, height) {
        const { nodes, edges } = JSON.parse(JSON.stringify(graph));
        const centerX = width / 2;
        const centerY = height / 2;
        const radius = Math.min(width, height) * 0.35;

        nodes.forEach((node, index) => {
          const angle = (2 * Math.PI * index) / nodes.length;
          node.x = centerX + radius * Math.cos(angle);
          node.y = centerY + radius * Math.sin(angle);
        });

        return { nodes, edges };
      }

      // 分层布局
      hierarchicalLayout(graph, width, height) {
        const { nodes, edges } = JSON.parse(JSON.stringify(graph));

        // 计算每个节点的度数来决定层次
        const degrees = {};
        nodes.forEach(node => degrees[node.id] = 0);
        edges.forEach(edge => {
          degrees[edge.source]++;
          degrees[edge.target]++;
        });

        // 按度数排序并分配到6层
        const sortedNodes = [...nodes].sort((a, b) => degrees[b.id] - degrees[a.id]);
        const layerSize = Math.ceil(nodes.length / 6);

        for (let i = 0; i < 6; i++) {
          const layerNodes = sortedNodes.slice(i * layerSize, (i + 1) * layerSize);
          const y = (height / 7) * (i + 1);

          layerNodes.forEach((node, index) => {
            node.x = (width / (layerNodes.length + 1)) * (index + 1);
            node.y = y;
          });
        }

        return { nodes, edges };
      }

      // 计算边交叉数
      calculateCrossings(layout) {
        const { edges } = layout;
        let crossings = 0;

        for (let i = 0; i < edges.length; i++) {
          for (let j = i + 1; j < edges.length; j++) {
            if (this.edgesIntersect(edges[i], edges[j], layout.nodes)) {
              crossings++;
            }
          }
        }

        return crossings;
      }

      // 检查两条边是否相交
      edgesIntersect(edge1, edge2, nodes) {
        const node1a = nodes[edge1.source];
        const node1b = nodes[edge1.target];
        const node2a = nodes[edge2.source];
        const node2b = nodes[edge2.target];

        return this.lineIntersect(
          node1a.x, node1a.y, node1b.x, node1b.y,
          node2a.x, node2a.y, node2b.x, node2b.y
        );
      }

      // 线段相交检测
      lineIntersect(x1, y1, x2, y2, x3, y3, x4, y4) {
        const denom = (x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4);
        if (Math.abs(denom) < 1e-10) return false;

        const t = ((x1 - x3) * (y3 - y4) - (y1 - y3) * (x3 - x4)) / denom;
        const u = -((x1 - x2) * (y1 - y3) - (y1 - y2) * (x1 - x3)) / denom;

        return t > 0 && t < 1 && u > 0 && u < 1;
      }

      // 计算布局质量指标
      calculateMetrics(layout) {
        const crossings = this.calculateCrossings(layout);
        const edgeLength = this.calculateAverageEdgeLength(layout);
        const nodeSpread = this.calculateNodeSpread(layout);

        return {
          crossings,
          avgEdgeLength: Math.round(edgeLength),
          nodeSpread: Math.round(nodeSpread * 100) / 100
        };
      }

      calculateAverageEdgeLength(layout) {
        const { nodes, edges } = layout;
        let totalLength = 0;

        edges.forEach(edge => {
          const source = nodes[edge.source];
          const target = nodes[edge.target];
          const length = Math.sqrt(
            Math.pow(source.x - target.x, 2) +
            Math.pow(source.y - target.y, 2)
          );
          totalLength += length;
        });

        return totalLength / edges.length;
      }

      calculateNodeSpread(layout) {
        const { nodes } = layout;
        let minDist = Infinity;

        for (let i = 0; i < nodes.length; i++) {
          for (let j = i + 1; j < nodes.length; j++) {
            const dist = Math.sqrt(
              Math.pow(nodes[i].x - nodes[j].x, 2) +
              Math.pow(nodes[i].y - nodes[j].y, 2)
            );
            minDist = Math.min(minDist, dist);
          }
        }

        return minDist;
      }

      // 渲染可视化
      render() {
        const container = document.getElementById('layoutContainer');
        container.innerHTML = '';

        const currentGraph = this.datasets[this.currentDataset];
        const width = 380;
        const height = 380;

        // 三种布局
        const layouts = [
          { name: '混合布局', method: this.hybridLayout.bind(this), color: '#667eea' },
          { name: '圆形布局', method: this.circularLayout.bind(this), color: '#4ecdc4' },
          { name: '分层布局', method: this.hierarchicalLayout.bind(this), color: '#ff6b6b' }
        ];

        layouts.forEach(layout => {
          const layoutData = layout.method(currentGraph, width, height);
          const metrics = this.calculateMetrics(layoutData);

          const section = document.createElement('div');
          section.className = 'layout-section';
          section.innerHTML = `
                        <div class="layout-title" style="color: ${layout.color}">${layout.name}</div>
                        <svg id="${layout.name.replace(' ', '-')}-svg"></svg>
                        <div class="stats">
                            <div class="stat-item">
                                <span class="stat-label">边交叉数:</span>
                                <span class="stat-value">${metrics.crossings}</span>
                            </div>
                            <div class="stat-item">
                                <span class="stat-label">平均边长:</span>
                                <span class="stat-value">${metrics.avgEdgeLength}</span>
                            </div>
                            <div class="stat-item">
                                <span class="stat-label">节点分散度:</span>
                                <span class="stat-value">${metrics.nodeSpread}</span>
                            </div>
                        </div>
                        <div class="legend" id="${layout.name.replace(' ', '-')}-legend"></div>
                    `;

          container.appendChild(section);
          this.drawGraph(layoutData, `${layout.name.replace(' ', '-')}-svg`, layout.color);
        });

        // 保存结果用于分析
        this.results[this.currentDataset] = {
          hybrid: this.calculateMetrics(layouts[0].method(currentGraph, width, height)),
          circular: this.calculateMetrics(layouts[1].method(currentGraph, width, height)),
          hierarchical: this.calculateMetrics(layouts[2].method(currentGraph, width, height))
        };
      }

      // 绘制图形
      drawGraph(layout, svgId, primaryColor) {
        const svg = d3.select(`#${svgId}`);
        svg.selectAll("*").remove();

        const { nodes, edges } = layout;

        // 绘制边
        const links = svg.selectAll('.link')
          .data(edges)
          .enter()
          .append('line')
          .attr('class', 'link')
          .attr('x1', d => nodes[d.source].x)
          .attr('y1', d => nodes[d.source].y)
          .attr('x2', d => nodes[d.target].x)
          .attr('y2', d => nodes[d.target].y);

        // 绘制节点
        const nodeElements = svg.selectAll('.node')
          .data(nodes)
          .enter()
          .append('circle')
          .attr('class', d => `node community-${d.community}`)
          .attr('cx', d => d.x)
          .attr('cy', d => d.y)
          .attr('r', 6);

        // 添加动画效果
        if (this.animationEnabled) {
          nodeElements
            .attr('r', 0)
            .transition()
            .duration(800)
            .delay((d, i) => i * 20)
            .attr('r', 6);

          links
            .attr('stroke-opacity', 0)
            .transition()
            .duration(1000)
            .delay(500)
            .attr('stroke-opacity', 0.6);
        }

        // 添加图例
        this.addLegend(svgId.replace('-svg', '-legend'), nodes);
      }

      // 添加图例
      addLegend(legendId, nodes) {
        const legend = document.getElementById(legendId);
        const communities = [...new Set(nodes.map(n => n.community))];

        legend.innerHTML = communities.map(community => `
                    <div class="legend-item">
                        <div class="legend-color community-${community}"></div>
                        <span>社区 ${community}</span>
                    </div>
                `).join('');
      }
    }

    // 全局实例
    let layoutComparison;

    // 初始化
    document.addEventListener('DOMContentLoaded', () => {
      layoutComparison = new GraphLayoutComparison();
    });

    // 控制函数
    function generateNewData() {
      layoutComparison.currentDataset = (layoutComparison.currentDataset + 1) % 10;
      layoutComparison.render();
    }

    function toggleAnimation() {
      layoutComparison.animationEnabled = !layoutComparison.animationEnabled;
      const button = event.target;
      button.textContent = layoutComparison.animationEnabled ? '⚡ 关闭动画' : '⚡ 开启动画';
    }

    function exportResults() {
      const results = layoutComparison.results.filter(r => r);
      if (results.length === 0) {
        alert('暂无数据可导出，请先生成一些布局！');
        return;
      }

      // 计算平均指标
      const avgResults = {
        hybrid: { crossings: 0, avgEdgeLength: 0, nodeSpread: 0 },
        circular: { crossings: 0, avgEdgeLength: 0, nodeSpread: 0 },
        hierarchical: { crossings: 0, avgEdgeLength: 0, nodeSpread: 0 }
      };

      results.forEach(result => {
        Object.keys(avgResults).forEach(layout => {
          Object.keys(avgResults[layout]).forEach(metric => {
            avgResults[layout][metric] += result[layout][metric];
          });
        });
      });

      Object.keys(avgResults).forEach(layout => {
        Object.keys(avgResults[layout]).forEach(metric => {
          avgResults[layout][metric] = Math.round(avgResults[layout][metric] / results.length * 100) / 100;
        });
      });

      // 显示结果
      const resultText = `
布局算法比较(${results.length}组数据平均):

混合布局:
- 边交叉数: ${avgResults.hybrid.crossings}
- 平均边长: ${avgResults.hybrid.avgEdgeLength}
- 节点分散度: ${avgResults.hybrid.nodeSpread}

圆形布局:
- 边交叉数: ${avgResults.circular.crossings}
- 平均边长: ${avgResults.circular.avgEdgeLength}
- 节点分散度: ${avgResults.circular.nodeSpread}

分层布局:
- 边交叉数: ${avgResults.hierarchical.crossings}
- 平均边长: ${avgResults.hierarchical.avgEdgeLength}
- 节点分散度: ${avgResults.hierarchical.nodeSpread}

结论:
混合布局在边交叉数方面表现${avgResults.hybrid.crossings < avgResults.circular.crossings && avgResults.hybrid.crossings < avgResults.hierarchical.crossings ? '最优' : '良好'}，
同时保持了良好的节点分散度和合理的边长分布。
            `;

      alert(resultText);
      console.log('详细结果:', results);
    }
  </script>
</body>

</html>